package com.lw.leetcode.stack.c;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 2281. 巫师的总力量和
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/24 13:14
 */
public class TotalStrength {

    public static void main(String[] args) {
        TotalStrength test = new TotalStrength();

        // 44
//        int[] arr = {1, 3, 1, 2};

        // 963380434
//        int[] arr = {1, 3, 1, 2, 43, 567, 3, 768, 45, 9, 56, 798, 996, 745, 34, 6890, 34545, 4543};

        // 901004969
        int[] arr = {515716246, 870080294, 431335481, 926634238, 460913337, 651211175, 519374881, 940216981, 9588873, 998780625, 243271245, 469031226, 847056547, 515931459, 428862338, 972891012, 801029685, 599837130, 591294043, 742656093, 699007873, 268174322, 876242054, 527393867, 616624093, 138587673, 596105348, 894305001, 491858725, 841020178, 815216895, 788635687, 507623320, 503801089, 986853788, 300713893, 808225436, 142655969, 170957440, 911317836, 580484062, 928945042, 912943707, 395102588, 514965110, 64371854, 597273331, 733100727, 713400953, 506612011, 309022186, 370952590, 619731961, 910067490, 725787720, 809509170, 432739447, 723135757, 767230754, 244044092, 191702392, 753984672, 11485611, 88940627, 375048098, 629865560, 703602373, 853281423, 376354233, 333173351, 918565260, 312414626, 840503155, 864287778, 297754683, 611909601, 339738292, 442192746, 248065109, 210905383, 62636489, 169627712, 673078107, 423601036, 743733986, 384626421, 780427170, 199745095, 473050307, 676110803, 923659550, 535769404, 356145389, 170423998, 898098867, 611851795, 960595844, 954539927, 792452644};

        // 310096695
//        int[] arr = {515716246, 870080294, 431335481, 926634238, 460913337, 651211175};

        // 494309947
//        int[] arr = {515716246, 870080294, 926634238};

        int i = test.totalStrength(arr);
        System.out.println(i);
    }

    public int totalStrength(int[] strength) {
        int length = strength.length;
        long[] arr = new long[length + 1];
        long[] all = new long[length + 1];
        long[] counts = new long[length + 1];
        for (int i = 1; i <= length; i++) {
            arr[i] = (arr[i - 1] + (long) strength[i - 1] * i) % 1000000007;
            all[i] = (all[i - 1] + strength[i - 1]) % 1000000007;
        }
        Stack<Long> stack = new Stack<>();
        Stack<Integer> index = new Stack<>();
        Stack<Long> sum = new Stack<>();
        stack.add(0L);
        index.add(0);
        sum.add(0L);
        for (int i = 0; i < length; i++) {
            long v = strength[i];
            while (stack.peek() >= v) {
                stack.pop();
                index.pop();
                sum.pop();
            }
            v %= 1000000007;
            int peek = index.peek();
            long a = ((((arr[i + 1] - arr[peek]) - (all[i + 1] - all[peek]) * peek) % 1000000007) * v) % 1000000007;
            long b = counts[peek];
            long c = sum.peek() * (all[i + 1] - all[peek]) ;

            counts[i + 1] = ((a + b + c) % 1000000007) + 1000000007;

            stack.add(v);
            index.add(i + 1);
            sum.add((sum.peek() + v * (i - peek + 1)) % 1000000007);
        }
        long s = 0;
        for (long count : counts) {
            s = (s + count) % 1000000007;
        }
        return (int) s;
    }

}
